package dp.simple;

/**
 * 第N个泰波那契数
 * 示例 1：
 *
 * 输入：n = 4
 * 输出：4
 * 解释：
 * T_3 = 0 + 1 + 1 = 2
 * T_4 = 1 + 1 + 2 = 4
 * 示例 2：
 *
 * 输入：n = 25
 * 输出：1389537
 * 链接：https://leetcode-cn.com/problems/n-th-tribonacci-number
 */
public class NthTribonacciNumber_1137 {

    public int tribonacci(int n) {
        int t0 = 0, t1 = 1, t2 = 1;
        int sum = t0 + t1 + t2;
        int i = 3;
        while(i < n) {
            t0 = t1;
            t1 = t2;
            t2 = sum;
            sum = t0 + t1 + t2;
            i++;
        }
        return sum;
    }

    public static void main(String[] args) {
        NthTribonacciNumber_1137 n = new NthTribonacciNumber_1137();
        System.out.println(n.tribonacci(25));
    }
}
